In order to facilitate the printing of images, it has long been desirable to convert an image having continuous tones ("the contone image") into an image having halftones. For example, a black & white picture is reproduced in a newspaper as a grid or array of black "spots", with the lighter areas having small spots and the darker areas having larger spots. For the very dark areas of a halftone image, the larger spots will run into one another so that the dark area looks like small white spots on a black field.
With the advent of computers, it is desirable for graphic artists to manipulate contone images and print them as halftone images. However, commercial computer printers and typesetters are incapable of printing individual halftone spots in an infinite number of sizes. Instead, each spot of a picture is in turn comprised of discrete smaller dots or "pixels". A pixel is generally the smallest mark a printer or typesetter can make, and, therefore, every spot will be collection of pixels.
FIG. 1 illustrates how one such spot may be made up of individual pixels. A grid 100 is comprised of a set of 100 contiguous pixels, and therefore, is capable of representing 101 shades of gray from totally light and white (0% gray and no pixels darkened) to totally dark and black (100% gray and all pixels darkened). For every 1% increase in darkness, one pixel will be darkened. For example, at 1% gray, a single pixel 1' is darkened. At 2% gray, pixel 2' is darkened as well, so that the spot is comprised of two pixels. At 10% gray, ten pixels 1'-10' are darkened. Pixels are either dark or not dark, and are not individually capable of representing shades of gray.
Rather than darkening a random pixel for every increase in gray level, it is preferable for the pixels to be darkened in a specific order pursuant to a "spot function". The order of darkening pixels in FIG. 1 reflects a spot function which attempts to maintain a generally circular shape as the spot increases in size. Topological curves (labeled from 10% to 100% in increments of 10%) generally define the outline of the spot as it increases in gray level. At 10% gray, the darkened pixels substantially conform with the 10% curve, and form a nearly circular spot around the center 110 of the spot function. At 20% gray, the darkened pixels form a slightly larger spot which substantially conforms with the 20% curve. At 50% gray, the pixels form a spot which is in substantially the shape of a diamond. At 90% gray, nearly all of the pixels are darkened except for 10 pixels 91'-100', these pixels being evenly dispersed at the four corners of the spot.
In the interest of speed, it is often desirable to store the pixels' representation of the spot function in memory for later use. To do so, the spot function is evaluated at the location of each pixel in the cell, the pixels are rank ordered according to their respective spot function values, and a threshold value from 0% to 100% is assigned to each pixel according to its rank. Where spot function values are identical for multiple pixels in a spot, their order can be determined by secondary considerations which may be arbitrary. In this way, each pixel has an associated "threshold value" which is equal to the gray level at which that pixel is darkened. FIG. 2. If a spot which represents a gray level of 75% is desired, the spot is created by darkening every pixel with a threshold value of 75% or less. A 75% gray level spot is indicated by outline 210. A single collection of pixels with threshold values representing a spot function is defined herein as a "halftone cell" or "cell". As defined herein, the terms "spot function" and "cell" are often interchangeable, as a cell is a quantized representation of a spot function, and the threshold values of the pixels map the spot function.
In this manner, a "digital screen" is created. A digital screen is an array of cells with pixels having threshold values. Each pixel has a set position and a set threshold value within the cell. Likewise, each cell has a set position within the digital screen. To create a halftone image, a contone image is broken down into an array of pixel-sized samples, and the gray level of each contone sample is stored. Next, each contone sample is compared with the threshold value of one pixel, and the pixel is darkened if the gray level of the contone sample is greater than the threshold value of the pixel. All the pixels of the digital screen are at set positions with respect to one another, such that a contone sample from the "top-left" of the picture would be compared with a pixel at the "top-left" of the digital screen. In other words, each digital screen pixel has a position which corresponds with and is associated with a position on the original contone picture.
FIG. 3 illustrates a halftone image represented by spots. FIG. 3 was created by comparing a picture having a consistent 5% gray value to a digital screen containing a 3-by-3 array of cells. Each cell contained 100 pixels, and only the pixels with threshold values of 5% or less were darkened. Accordingly, a 3-by-3 array of spots was created, each spot having five pixels. FIG. 4 was created by comparing a picture having a consistent 95% gray value to the same digital screen. All the pixels with gray values of 95% or less were darkened. Although the resulting halftone image is really comprised of nine large spots, the naked eye perceives the halftone image as being smaller white spots on a field of black.
Because a halftone image may be comprised of many thousands of spots, and because each spot is in turn comprised of many pixels, storing the values of a digital screen takes up a substantial amount of memory. Therefore, it is preferable to store a relatively small threshold array which may be replicated in two dimensions to "tile" a digital screen. These small arrays may consist of as little as a partial cell, or exactly one cell, or many cells grouped together. In many cases it is preferable to use arrays that consist of a large number of cells, which are often called "macrocells" or "supercells", because they offer the greatest flexibility for representing different screen frequencies and angles.
Unfortunately, the creation of supercells often produces undesirable side effects in the resulting halftone image, especially when a cell ideally includes a non-integer number of pixels. FIG. 5 illustrates a supercell which includes a 4-by-4 array of cells, each cell being associated with one spot function (the ideal boundaries of the cells are shown as solid lines). The supercell also includes a 25-by-25 array of pixels (the boundaries of the pixels are shown as short dashed lines). The ideal boundaries of the cells do not correspond exactly with the boundaries of the pixels. Instead, each cell is 6.25 pixels wide and 6.25 pixels high. Because of this non-integer relationship, a substantial amount of effort in the art has been devoted to methods which decide how a pixel which resides in two or more ideal cells is allocated to one cell or the other.
Aside from the border pixel difficulties, the quantization of non-integer ideal cells also creates difficulties at the endtones, i.e., those gray values close to 0% or 100% gray. The problem is due to the fact that the center of the spot function will not correspond with the same pixel for each cell. The center 311 of the spot function of cell 310 is substantially centered within one pixel 301. Therefore, for cell 310, it is clear that pixel 301 should be the first pixel darkened in cell 310. However, it is not so clear which pixel should be the first pixel darkened for the other cells. Center 321 of cell 320 lies nearly at the border of four pixels 302-305. Accordingly, when the threshold values are allocated to the pixels of cell 320, the order of pixel darkening may be different for cell 320 than for cell 310. This quantization problem creates Moire patterns at the endtones.
FIG. 6 illustrates the Moire patterns created at the endtones when a contone image of about 6% is compared to the supercell of FIG. 5. Although each of the cells only darkens two pixels to make a spot, the orientation of the spots are different. For example, the four spots 501-504 in the lower-left quadrant of the halftone image are all horizontal, as are spots 505-508 in the top-right quadrant of the halftone image. The other spots, on the other hand, are all vertical. A predictable pattern of orientation is created at this light gray value, and the Moire pattern will be apparent and distracting to the naked eye. Even if the naked eye were not able to perceive the pattern across a single supercell, the pattern would become immediately apparent when the supercell is repeated across the entire digital screen and, consequently, the halftone image. A similar pattern might also be apparent at very dark gray values.
Consequently, there is a need for a method and system of creating digital screens which eliminate the visible Moire patterns at the endtones. One well known technique relies on the introduction of "noise". In a typical implementation of digital screening, the "noise" is in the form of a pseudo-random value of appropriate amplitude which is additively or multiplicatively combined with either the contone values of the image to be screened or with the threshold values in the digital screen. In this way the visibility of the Moire can be obscured but at the cost of introducing a "grainy" appearance due to the added noise. Therefore, there is still a need for a method and system of creating digital screens which prevent the creation of Moire patterns at the endtones.
In addition to the Moire patterns created by the quantization of an endtone spot, other Moire patterns may be created due to the rate at which the spots grow. As explained above, the average number of pixels per halftone cell may be nonintegral. Therefore, the actual number of pixels per cell varies. Since each spot must grow from 0% to 100% in response to a desired gray level, each spot must consequently grow at a different rate.
The different growth rates of spots may present Moire patterns. This is particularly troublesome in the endtones where the pixels of a cell are predominantly white or black and the difference in pixels added is proportionally large to the size of the spot. Furthermore, since the distribution of spot sizes within the supercell is regular across the printed halftone image, the artifacts can have a spatial period as large as the supercell. Since the spatial frequency will be low compared to the screen frequency, the artifacts are readily seen.
Consequently, there is a need for a method of growing a halftone spot which prevents the creation of Moire patterns.
The present invention provides methods to meet those needs.